package stackAndQueue.q1_getMinStack;

import java.util.Stack;

/**
 * Project：algorithm
 * Date：2024/6/3
 * Time：21:39
 * Description：实现一个特殊的栈，在实现栈的基本功能上，再实现返回栈中最小的元素
 * 要求：
 *     1. pop、push、getMin操作的时间复杂度都是O(1)
 *     2. 设计的栈类型可以使用现成的栈结构
 * 解法：双栈
 *     设计两个栈，一个正常压入stackData，一个栈用于保存每一步的最小值stackMin
 *     压入规则：newNum，正常压入stackData，如果stackMin为空，直接压入stackMin；不为空则比较两者大小，小于或等于当前栈顶的数，也压入
 *     弹出规则：弹出stackData的value时，当value等于stackMin栈顶的元素时，弹出stackMin
 * @author Cao Jiwen
 * @version 1.0
 */
public class GetMinStack {
    private final Stack<Integer> stackData;
    private final Stack<Integer> stackMin;

    public GetMinStack() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }

    /**
     * 压栈
     * @param newNum 压栈元素
     */
    public void push(int newNum){
        this.stackData.push(newNum);
        if (this.stackMin.isEmpty()){
            this.stackMin.push(newNum);
        }else if (newNum < getMin()){
            this.stackMin.push(newNum);
        }
    }

    /**
     * 弹栈
     * @return 弹出的元素
     */
    public int pop(){
        if (this.stackData.isEmpty()){
            throw new RuntimeException("StackData is empty.");
        }
        Integer value = this.stackData.pop();
        if (value == getMin()){
            this.stackMin.pop();
        }
        return value;
    }

    /**
     * @return 获取栈最小值（获取stackMin栈顶元素值）
     */
    public int getMin(){
        if (stackMin.isEmpty()){
            throw new RuntimeException("StackMin is empty.");
        }
        return this.stackMin.peek();
    }
}
